package rjp.solver;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

import rjp.map.CachingSantaMap;
import rjp.map.SantaMap;
import rjp.solution.Solution;

public class NearestNeighbourSolver implements Solver{
	
	int startA;
	int startB;
	
	public NearestNeighbourSolver(SantaMap map, int startA, int startB)
	{
		this.startA=startA;
		this.startB=startB;
	}
	
	public NearestNeighbourSolver(SantaMap map)
	{
		Random random=new Random();
		this.startA=(int) (random.nextFloat()*map.size());
		this.startB=(int) (random.nextFloat()*map.size());
	}

	@Override
	public Solution solve(SantaMap map) throws Exception {
		List<Integer> pathA=new ArrayList<Integer>(map.size());
		List<Integer> pathB=new ArrayList<Integer>(map.size());
		
		Set<Integer> unusedA=new HashSet<Integer>(map.size());
		Set<Integer> unusedB=new HashSet<Integer>(map.size());
		
		Map<Integer, Set<Integer>> usedConnections=new HashMap<Integer, Set<Integer>>(map.size());
		for(int i =0; i<map.size(); i++)
		{
			usedConnections.put(new Integer(i), new HashSet<Integer>());
			unusedA.add(new Integer(i));
			unusedB.add(new Integer(i));
		}
		
		pathA.add(new Integer(this.startA));
		unusedA.remove(new Integer(this.startA));
		
		pathB.add(new Integer(this.startB));
		unusedB.remove(new Integer(this.startB));
		
		for(int i=0; i<map.size()-1; i++)
		{
			if(i%1000==0)
			{
				System.out.println(i);
			}
			int ca=map.getClosestInSet(pathA.get(i), unusedA, usedConnections.get(pathA.get(i)));
			pathA.add(ca);
			unusedA.remove(ca);
			usedConnections.get(pathA.get(i)).add(ca);
			usedConnections.get(ca).add(pathA.get(i));
			
			int cb=map.getClosestInSet(pathB.get(i), unusedB, usedConnections.get(pathB.get(i)));
			pathB.add(cb);
			unusedB.remove(cb);
			usedConnections.get(pathB.get(i)).add(cb);
			usedConnections.get(cb).add(pathB.get(i));
		}
		
		return new Solution(map, pathA, pathB);
	}

}
